package A1_单调栈;

import java.util.Arrays;
import java.util.Deque;
import java.util.HashMap;
import java.util.LinkedList;

public class LC_496下一个更大元素I {
    public static void main(String[] args){
        int[] res=nextGreaterElement(new int[]{2, 4},new int[]{1,2,3,4} );
        System.out.println(res);
    }
    public static int[] nextGreaterElement(int[] nums1, int[] nums2) {
        Deque<Integer> st=new LinkedList<>();
        HashMap<Integer,Integer> map=new HashMap<>();
        int[] res=new int[nums1.length];
        Arrays.fill(res,-1);
        if(nums1.length==0)
            return res;
        for(int i=0;i<nums1.length;i++)
            map.put(nums1[i],i);
        st.push(0);
        for(int i=1;i<nums2.length;i++){
            if(nums2[i]<=nums2[st.peek()])
                st.push(i);
            else{
                while(!st.isEmpty() && nums2[i]>nums2[st.peek()]){
                    if(map.containsKey(nums2[st.peek()]))
                    {
                        int index=map.get(nums2[st.peek()]);//返回key对应的value
                        res[index]=nums2[i];
                    }
                    st.pop();
                }
                st.push(i);
            }
        }
        return res;
    }
}
